package euler.p051_100;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;

import euler.MainEuler;
import euler.helper.Utils;

public class Euler067 extends MainEuler {

    /*
        By starting at the top of the triangle below and
        moving to adjacent numbers on the row below,
        the maximum total from top to bottom is 23.

        3
        7 4
        2 4 6
        8 5 9 3

        That is, 3 + 7 + 4 + 9 = 23.

        Find the maximum total from top to bottom in
        http://projecteuler.net/project/triangle.txt
     */
    public String resolve() throws IOException {
        String filePath = Utils.pathToFiles + "triangle.txt";

        BufferedReader br = null;

        int[][] triangle = new int[100][];

        try {
            br = new BufferedReader(new FileReader(new File(filePath)));
            String strLine;
            int i = 0;
            while ((strLine = br.readLine()) != null)   {

                String[] split = strLine.split(" ");

                int[] row = new int[split.length];

                for (int j = 0; j < row.length; j++) {
                    row[j] = Integer.valueOf(split[j]);
                }

                triangle[i++]=row;
            }
        } finally {
            if (br != null) {
                br.close();
            }
        }

        int[][] maxSums = new int[100][];
        fillMaxSums(triangle,maxSums);

        return String.valueOf(maxSums[0][0]);
    }

    private static void fillMaxSums(int[][] triangle, int[][] maxSums) {

        maxSums[maxSums.length - 1] = triangle[triangle.length - 1];

        for (int i = maxSums.length - 2; i >= 0; i--) {
            int[] row = new int[triangle[i].length];

            for (int j = 0; j < row.length; j++) {
                row[j] = triangle[i][j] + Math.max(maxSums[i + 1][j], maxSums[i + 1][j + 1]);
            }

            maxSums[i] = row;
        }
    }
}
